Propriétés du PGCD

Propriétés

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) .

• Si \((a;b) \neq (0;0)\) , 
  alors \(\mathrm{PGCD}(\left\vert a \right\vert;\left\vert b \right\vert)=\mathrm{PGCD}(a;b)=\mathrm{PGCD}(\left\vert a \right\vert;b)=\mathrm{PGCD}(a;\left\vert b \right\vert)\) .
• Si \(a \neq 0\) ,
  alors \(\mathrm{PGCD}(a;0)=\left\vert a \right\vert\) .
• Si \(a \neq 0\) et \(b \neq 0\) ,
  alors \(b\) divise \(a\) si, et seulement si, \(\mathrm{PGCD}(a;b)=\left\vert b \right\vert\) .

Démonstration

• Supposons que \((a;b) \neq (0;0)\) .
  On sait que \(\mathscr{D}(a)=\mathscr{D}(-a)=\mathscr{D}(\left\vert a \right\vert)\) et de même pour \(b\) .
  Par conséquent, \(\begin{align*} \mathscr{D}(\left\vert a \right\vert;\left\vert b \right\vert) =\mathscr{D}(\left\vert a \right\vert) \cap \mathscr{D}(\left\vert b \right\vert) =\mathscr{D}(a) \cap \mathscr{D}(b) =\mathscr{D}(a;b). \end{align*}\)  
  Les ensembles \(\mathscr{D}(\left\vert a \right\vert;\left\vert b \right\vert)\) et \(\mathscr{D}(a;b)\) étant égaux, ils ont le même plus grand élément, c'est-à-dire que \(\mathrm{PGCD}(\left\vert a \right\vert;\left\vert b \right\vert)=\mathrm{PGCD}(a;b)\) .
  Même principe pour les deux autres égalités.
• Supposons que \(a \neq 0\) .
  On a \(\mathscr{D}(a;0)=\mathscr{D}(a)\) . Or, pour tout \(d \in \mathscr{D}(a)\) , on a \(d \leqslant \left\vert a \right\vert\) .
  L'ensemble \(\mathscr{D}(a)\) est donc majoré par \(\left\vert a \right\vert\) .
  De plus, \(\left\vert a \right\vert \in \mathscr{D}(\left\vert a \right\vert)=\mathscr{D}(a)\) .
  Par conséquent, \(\left\vert a \right\vert\) est le plus grand élément de \(\mathscr{D}(a)\) , donc \(\mathrm{PGCD}(a;0)=\left\vert a \right\vert\) .
• Supposons que \(a \neq 0\) et \(b \neq 0\) .
  On procède par double implication.
  \([\Rightarrow]\) On suppose que b divise a.
  Soit \(d \in \mathscr{D}(a;b)\) . Alors \(d \in \mathscr{D}(b)\) , donc \(d \leqslant \left\vert b \right\vert\) .
  L'ensemble \(\mathscr{D}(a;b)\) est donc majoré par \(\left\vert b \right\vert\) .
  De plus, comme \(b\) divise \(a\) , on a \(\left\vert b \right\vert \in \mathscr{D}(\left\vert a \right\vert)=\mathscr{D}(a)\) .
  Or \(\left\vert b \right\vert \in \mathscr{D}(\left\vert b \right\vert)=\mathscr{D}(b)\) . On en déduit que \(\left\vert b \right\vert \in \mathscr{D}(a;b)\) .
  Finalement, \(\left\vert b \right\vert\) est le plus grand élément de \(\mathscr{D}(a;b)\) , donc \(\mathrm{PGCD}(a;b)=\left\vert b \right\vert\) .
  \([\Leftarrow]\) On suppose que \(\mathrm{PGCD}(a;b)=\left\vert b \right\vert\) .
  Alors \(\left\vert b \right\vert \in \mathscr{D}(a;b)\) , donc \(\left\vert b \right\vert \in \mathscr{D}(a)\) .
  Comme \(\mathscr{D}(a)=\mathscr{D}(-a)\) , on en déduit que \(b \in \mathscr{D}(a)\) , c'est-à-dire que \(b\) divise \(a\) .